<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>trie</title>
</head>

<body>
  <script>
    let $ = Symbol('$')
    class Trie {
      constructor() {
        this.root = Object.create(null)
      }
      insert(word) {
        let node = this.root;
        for (let c of word) {
          if (!node[c]) {
            node[c] = Object.create(null)
          }
          node = node[c]
        }
        if (!($ in node)) {
          node[$] = 0;
        }
        node[$]++
      }
      most() {
        let max = 0;
        let maxWord = null;
        let visit = (node, word) => {
          if (node[$] && node[$] > max) {
            max = node[$]
            maxWord = word
          }
          for (let p in node) {
            visit(node[p], word + p)
          }
        }
        visit(this.root, '')
        console.log(maxWord, max)
      }
      //查询出现4次以上
      most2() {
        let maxWordArr = []
        let visit = (node, word) => {
          if (node[$] && node[$] > 4) {
            maxWordArr.push(word)
          }
          for (let p in node) {
            visit(node[p], word + p)
          }
        }
        visit(this.root, '')
        console.log(maxWordArr)

      }
      most3() {
        let mostWordArr = []
        let visit = (node, word) => {
          if (node[$] && word.substr(0, 2) == 'ab') {
            mostWordArr.push(word)
          }
          for (let p in node) {
            visit(node[p], word + p)
          }
        }
        visit(this.root, '')
        console.log(mostWordArr,mostWordArr.length-1)
      }
    }

    function randomWord(length) {
      let s = '';
      for (let i = 0; i < length; i++) {
        s += String.fromCharCode(Math.random() * 26 + 'a'.charCodeAt(0))
      }
      return s
    }
    let tire = new Trie();
    for (let i = 0; i < 100000; i++) {
      tire.insert(randomWord(4))
    }
  </script>
</body>

</html>